package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/symmetric-tree/">对称二叉树(Symmetric Tree)</a>
 * <p>给你一个二叉树的根节点 root ， 检查它是否轴对称。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,2,3,4,4,3]
 *                  1
 *                /   \
 *               2     2
 *              / \   / \
 *             3   4 4   3
 *      输出：true
 *
 * 示例 2：
 *      输入：root = [1,2,2,null,3,null,3]
 *                  1
 *                /  \
 *               2    2
 *                \    \
 *                 3    3
 *      输出：false
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 1000] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 * <b>进阶：你可以运用递归和迭代两种方法解决这个问题吗？</b>
 *
 * @author c2b
 * @since 2023/10/17 18:51
 */
public class LC0101SymmetricTree_S {

    static class Solution {
        public boolean isSymmetric(TreeNode root) {
            //return isSymmetricByIteration(root);
            return isSymmetricByRecursion(root.left, root.right);
        }

        private boolean isSymmetricByIteration(TreeNode root) {
            if (root == null) {
                return true;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root.left);
            queue.offer(root.right);
            while (!queue.isEmpty()) {
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                // 可能还存在其他没比较的节点。继续下次循环
                if (left == null && right == null) {
                    continue;
                }
                if (left == null || right == null || left.val != right.val) {
                    return false;
                }
                queue.offer(left.left);
                queue.offer(right.right);
                queue.offer(left.right);
                queue.offer(right.left);
            }
            return true;
        }

        private boolean isSymmetricByRecursion(TreeNode left, TreeNode right) {
            if (left == null && right == null) {
                return true;
            }
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            return isSymmetricByRecursion(left.left, right.right) && isSymmetricByRecursion(left.right, right.left);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(9);
        root.left = new TreeNode(-42);
        root.right = new TreeNode(-42);

        root.left.left = null;
        root.left.right = new TreeNode(76);
        root.left.right.left = null;
        root.left.right.right = new TreeNode(13);

        root.right.left = new TreeNode(76);
        root.right.right = null;
        root.right.left.left = null;
        root.right.left.right = new TreeNode(13);

        Solution solution = new Solution();
        System.out.println(solution.isSymmetric(root));         // true
    }
}